In data exchange network, the key point that allows the data rapidly transmitted among ports is to record and learn all the net addresses effectively in order to find a destination port soon.
In a general data exchange network, the transmitted data is cut and packed, and every packet has a corresponding physical address. The data is transmitted from a node to another according to the physical addresses of the nodes. The physical addresses in different network are different in length. A 48-bit physical address is given as an example, which also occurs in Ether Network and means that there are 2.sup.48 possible addresses in the network. When a data is transmitted from a node A to a node B through path selection, it is necessary for the path selection to use a memory whose volume is 2.sup.48 bytes to judge which address is on a certain node. Therefore, an impossible huge memory is needed. Because of this, a path select table, i.e. a routing table, built according to hashing algorithm is adopted for processing the transmission among the nodes. A hashing address needed when accessing the physical address stored in the routing table is generated through a hashing function which is dependent on and obtained from the used method, e.g. an XOR or a CRC (Cyclic Redundancy Coding) method.
In general interworking unit, the way of processing the packet calling is learning or forwarding path selection, i.e. a leaning procedure or a routing procedure. The proceeding way of a learning and a routing procedures are shown respectively in FIGS. 1A and 1B. No matter which procedure is used for processing the packet calling 11 or 16, a hashing address 13 or 17 generated through a hashing function 12 is needed when accessing a physical address 15 or 18 corresponding to the hashing address 13 or 17 and being stored in the routing table 14. In the learning procedure, the port address 15 of a packed source address 11 is recorded in the routing table 14 to identify from which port the source address 11 comes. On the other hand, in the routing procedure, the port address 18 of a packed destination address 16 is requested from the routing table 14 to identify to which port the destination address 16 goes.
In conventional hashing algorithm, only one routing table is used for accessing physical addresses either in a learning procedure or in a routing procedure. Refer to FIG. 2 which is a flow chart showing a conventional routing procedure. A 48-bit physical address (b0 . . . b47) is divided into 3 16-bit parts (b0 . . . b15, b16 . . . b31, b32 . . . b47). The parts b32 . . . b47 and b16 . . . b31 are processed by XOR method to obtain an interim 16-bit part. The obtained 16-bit part and the part b0 . . . b15 are further processed by XOR method to thus obtain a 16-bit hashing address (A0 . . . A15). The system then picks n bits (n.ltoreq.16) of the hashing address (A0 . . . A15) to serve as a relative address for reading a 48-bit physical address in the routing table, then compares the physical address in the routing table with the destination address, and then reads and sends the port address also serving as a path select address header to a destination port to finish a packet calling process if the two physical addresses are identical. However, the two physical addresses are defined to conflict with each other if the two physical addresses are different, and a broadcasting step will be proceeded. From FIG. 2, it is found that the routing table stores therein the related data of each frame including the media access control address (MAC address) corresponding to the hashing address, a port ID identifying to which port the destination address goes, and a valid bit state. When the valid bit state is "1", the frame is defined to be effective; while the valid bit is "0", the frame is defined to be ineffective. On the other hand, in a conventional learning procedure, the source address is written into the corresponding address of the routing table and the aging is changed into zero if the physical address in the routing table is different from the source physical address. The routing table in the learning procedure stores therein the related data of each frame including the media access control address (MAC address) corresponding to the hashing address, a port ID identifying from which port the source address comes, an aging during which the source address should be stored, and a valid bit state. When the valid bit state is "1", the frame is defined to be effective; while the valid bit is "0", the frame is defined to be ineffective.
The conventional hashing algorithm has a shortcoming of high conflict probability, wherein the term "conflict" is defined as that different physical addresses through a hashing function obtain the same hashing address, and therefore correspond to the same physical address in the routing table. For example, there are two physical addresses A and B which through a hashing function obtain the same hashing address, i.e. the corresponding n bits of A and B after being hashed are identical. The conflict will be caused when destination addresses of two packets are respectively the two physical addresses. In detail, if A is stored in the routing table earlier than B in a learning procedure, B will superimpose A in the routing table when B is stored in the routing table to execute the modifying step. Moreover, at this time, the packet with the destination address A rather than B will be broadcasted in the proceeding routing procedure. Broadcasting means that the packet is sent to every port except the source port itself, and thus the throughput of the network will be lowered.
The relevant prior art of hashing algorithm is U.S. Pat. No. 5,027,350 entitled "Method And Apparatus For Providing A Local Area Network Bridge" issued to Marshall.
Marshall discloses a method and apparatus for routing data packets utilizing hashing algorithm by comparing the source and destination addresses. As is known, applying a hash algorithm can produce an event termed "a collision" wherein items hash to the same location in the table (col. 1, lines 43-46). Marshall discloses a method to reduce collision by using a plurality of hashing (Col. 4, lines 7-11). In Marshall's method, a plurality of independent hashing algorithms must be used for each of the Marshall's routing table and the volumes of the table must be the same (col. 1. lines 46-52; col. 4, lines 7-16; col. 6, lines 10-52).
However, different from the patent to Marshall, the present invention discloses a way for memory allocation to reduce the collision. The idea of the present invention comes from the concept of the back-up system. Here, a back-up routing tables (i.e. routing tables used in a bridge except for the primary routing table) is employed to store the items that hash to the same location in the primary table. As a result, it only use a hashing algorithm to find the respective location of the routing table for each incoming address. Moreover, it can use smaller volumes for back-up routing tables because the collision of items is expected to be rarely occurred in a LAN. Thus, the method for memory allocation, proposed in the present invention, can efficiently utilize memory as well as reduce the collision probability.
Therefore, it would like to emphasize that the present invention is superior to and different from Marshall's method in many ways.
i) The present invention only utilizes one hashing for a plurality of routing tables while Marshall's method must use an independent hashing algorithm for each of the routing table. Nevertheless, it is not easy to find a plurality of independent hashing algorithms.
ii) The resulting collision probability according to the present invention will be less than Marshall's method in most situations.